Graph data that represent the relationship of the elements of a complete configuration can be visualized by using nodes representing the elements and arcs connecting the nodes. The graphics displays used to visualize graph data can vary, and includes displays for the linked structure of web pages, for networks, such as those for financial, communication, transportation or social organizations, for data graphs for chemical or biological properties, for graphs showing the correlation of text data and image data, and for graphs used to delineate the operation of systems constituted by combinations of several relevant modules (e.g., the processing performed by a parallel processor). As a result, a demand exists for a computer display technique for graphics data that is applicable to a very wide range of fields.
The most important requirement for a graphics display technique is that “nodes and arcs in a graph be automatically so arranged in a display space that the graph is not misunderstood by a reader”. In order to resolve the problem this requirement presents, it is preferable that, to the extent possible, the following conditions be satisfied.                [Condition 1] The overlapping of neighboring nodes is prevented by, at the least, maintaining a constant distance between them.        [Condition 2] The total lengths of arcs are reduced by positioning the nodes they connect as closely together as is possible.        [Condition 3] Arcs do not overlap nodes at locations other than at end points.        
These conditions are shown in FIG. 21.
A well known, effective conventional method for obtaining a graph arrangement that best satisfies the above conditions provides for the use of an intermolecular force model and a spring model. That is, according to this method, the equation of motion is solved by using the intermolecular force model for the nodes of a graph and the spring model for the arcs of the graph, and then calculating appropriate positions for the nodes. As is shown in FIG. 21, for [Condition 1], according to which erroneous readings are avoided by providing a display in which nodes do not overlap, the intermolecular force model, when used for the nodes, serves as a repulsive force that prevents the overlapping of neighboring nodes.
Further, as is shown in FIG. 21, for [Condition 2], according to which visual apprehension is facilitated by a node arrangement in which nodes connected by arcs are positioned closely together, the spring model, when used for the arcs, serves as an attractive force that reduces the lengths of the arcs.
And finally, as is shown in FIG. 21, for [Condition 3], according to which erroneous readings are avoided by preventing arcs from overlapping nodes at locations other than at end points, in addition to using the intermolecular force model and the spring model, a predetermined distance is designated between arcs and nodes to produce a repulsive force that is exerted from the arcs to the nodes.
FIG. 22 is a diagram showing the state wherein the intermolecular force model is employed for the nodes in the graph and the spring model is employed for the arcs. As is shown in FIG. 22, the intermolecular force model provides a repulsive force that serves as a separating force for the nodes, and the spring model serves as a contracting force (an attractive force between the nodes) that reduces the lengths of the arcs.
The requests made for many applications are for a graphics display technique for the above graph data that will “quickly obtain a minimum required arrangement that can, at the least, prevent erroneous readings, regardless of whether an optimal arrangement is acquired”. As a specific example, for a graph of a size (several tens to several hundreds of nodes) that can be satisfactorily arranged in the window of the display device of a personal computer, it is requested that the arrangement results for the graph be obtained within a calculation time of several seconds, and that the “overlapping of nodes” and the “overlapping of a node and an arc” do not occur in the obtained arrangement.
In response to a tradeoff request for “the quality of the obtained arrangement” and “fast processing”, by the conventional graph data display method that uses dynamic models, such as the intermolecular force model and the spring model, satisfactory fast processing can not be performed, while the quality of what is displayed is satisfied to a degree. The calculation time required by this conventional method is O(N2), in the worst case, when the number of nodes is N. O(N2) means that a calculation can be performed within a period equivalent to constant number of times N2. Therefore, according to the conventional method, the calculation time rises dramatically in consonance with increases in the number of nodes.
The use of a method whereby a predetermined distance is provided between arcs and nodes, by using a repulsive force exerted by the arcs on the nodes, is especially not practical when the intent is the prevention of arc and node overlapping, because in this case there is a remarkable increase in the calculation time.
Further, although the acquisition of satisfactory arrangement results depends greatly on the initial node arrangement, no conventional method exists whereby it can be determined whether an initial arrangement is appropriate.
FIG. 23A is a diagram showing an example inappropriate initial arrangement of nodes. In the examples in FIGS. 23A to 23C, a node A and a node D are connected by an arc, and the attractive force for reducing the length acts on the arc. Therefore, it is preferable that the attractive force exerted by the arc AD be utilized to alter the graph and to provide the one shown in FIG. 23B or 23C. However, since movement of the node A is inhibited by the repulsive force exerted by the nodes B and C, frequently it is not possible to alter the state of the graph shown in FIG. 23A.
As is described above, according to the conventional graphics display method, a node arrangement that does not satisfy Conditions 1 and 2 tends to be output due to an inappropriate initial node arrangement.